package com.example.demo.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class Solution {
	public static void main(String[] args) {
		//Solution_1.testMethed();
		//Solution_2.testMethed();
		//Solution_3.testMethed();
		//Solution_4.testMethed();
		//Solution_5.testMethed();
		//Solution_6.testMethed();
		Solution_7.testMethed();
		
	}
}

/**
 * 题目描述：
 * 	给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
 * 注意:
 * 	假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−2的31次方,  2的31次方 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。
 * 解题思路：
 * 	1、转字符处理（会报异常）
 * 	2、数学逻辑计算
 * @author xiaoxin
 *
 */
class Solution_7 {
    public int reverse(int x) {
    	long tempReverse = 0;
    	int divisor = Math.abs(x);//除数
    	boolean falg = (divisor == x);
    	int remainder = 0;//余数
    	while(divisor > 0) {
    		remainder = divisor % 10;
    		divisor = divisor / 10;
    		tempReverse = tempReverse * 10 + remainder;
    	}
    	if (tempReverse >= Integer.MIN_VALUE && tempReverse <= Integer.MAX_VALUE) {
    		int reverse = (int) tempReverse;
			return falg ? reverse : -1 * reverse;
		}
    	System.out.println("不在范围内。。。");
        return 0;
    }
    
    public int reverse1(int x) {
    	String s = String.valueOf(x);
    	StringBuffer sb = new StringBuffer();
    	for(int index = s.length() - 1; index > 0; index--) {
    		sb.append(s.charAt(index));
    	}
    	String reverseStr = sb.toString();
    	int reverse = 0;
    	try {
    		if (s.charAt(0)=='-') {
    			reverse = Integer.valueOf(reverseStr) * (-1);
    		} else {
    			reverse = Integer.valueOf(reverseStr + s.charAt(0));
    		}
    	} catch (NumberFormatException e) {
    		System.out.println("不在范围内。。。");
    		return 0;
    	}
    	return reverse;
    }
    
    public static void testMethed() {
    	Solution_7 solution = new Solution_7();
    	int x = 1534236469;
    	int reverse1 = solution.reverse1(x);
    	System.out.println(reverse1);
    	int reverse = solution.reverse(x);
    	System.out.println(reverse);
    	System.out.println(Integer.MIN_VALUE);
    	System.out.println(Integer.MAX_VALUE);
    }
}

/**
 * 题目描述：
 * 	将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。
 * 示例：
 * 	输入: s = "LEETCODEISHIRING", numRows = 3
 * 	输出: "LCIRETOESIIGEDHN"
 * 解释:
 *  L   C   I   R
 *	E T O E S I I G
 *	E   D   H   N
 * 
 * 	输入: s = "LEETCODEISHIRING", numRows = 4
 * 	输出: "LDREOEIIECIHNTSG"
 * 解释:
 * 	L     D     R
 *	E   O E   I I
 *	E C   I H   N
 *	T     S     G
 * 解题思路：
 * 	1、输入字符和输出字符下标索引值有规律可寻
 * 	2、安题意输出整个Z矩阵，然后遍历
 * @author xiaoxin
 *
 */
class Solution_6 {
    public String convert(String s, int numRows) {//PAYPALISHIRING 3
    	if (numRows == 1) 
    		return s;
    	StringBuffer sb = new StringBuffer();
    	int length = s.length();                                           	
    	int tempIndex = 0;//索引值 											
    	int diff = 2 * (numRows - 1);//第一行和最后一行的索引差值，是固定的				
    	int dynamicDiff = 0;//中间行的差值，根据numRow值变化                                                                                  	
    	
    	for(int numRow = 0; numRow < numRows; numRow++) {					
    		tempIndex = numRow;												
    		dynamicDiff = 2 * numRow;
    		while(tempIndex < length) {										
    			sb.append(s.charAt(tempIndex));	
    			tempIndex += (numRow == 0 || numRow == (numRows - 1)) ? diff : dynamicDiff;
    		}
    	}
    	return sb.toString();
    }
    
    public String convert1(String s, int numRows) {//PAYPALISHIRING 3
    	if (numRows == 1) 
    		return s;
    	StringBuffer sb = new StringBuffer();
    	int length = s.length();                                           	
    	int diff = 2 * (numRows - 1);//第一行和最后一行的索引差值，是固定的				
    	
    	for(int numRow = 0; numRow < numRows; numRow++) {		
    		for(int index = 0; index < length; index++) {
    			if(index % diff == numRow || index % diff == (diff - numRow)) sb.append(s.charAt(index));
    		}
    	}
    	return sb.toString();
    }
    
    public static void testMethed() {
    	Solution_6 solution = new Solution_6();
    	String s = "PAYPALISHIRING";
    	int numRows = 4;
    	String convert = solution.convert(s, numRows);
    	System.out.println(convert);
    	String convert1 = solution.convert1(s, numRows);
    	System.out.println(convert1);
    }
}

/**
 * 题目描述：
 * 	给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
 * 示例：
 * 	输入: "babad"
 *	输出: "bab"
 *	注意: "aba" 也是一个有效答案。
 * 解题思路：
 * 	回文数概念：回文是一个正读和反读都相同的字符串
 * @author xiaoxin
 *
 */
class Solution_5 {
	
    /**
     * 暴力循环
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
    	String resultString = "";
    	int maxLength = 0;//记录回文数最大长度
    	int length = s.length();
    	for(int i = 0; i < length; i++) {
    		for(int j = i;j < length; j++) {
    			String tempString = s.substring(i, j + 1);
    			int tempLength = tempString.length();
    			boolean check = check(tempString);
    			if (check && tempLength > maxLength) {
    				maxLength = tempLength;
    				resultString = tempString;
				}
    		}
    	}
        return resultString;
    }
    
    /**
     * 中心扩散：
     * 	中心扩散法的想法很简单：遍历每一个索引，以这个索引为中心，利用“回文串”中心对称的特点，往两边扩散，看最多能扩散多远。要注意一个细节：回文串的长度可能是奇数，也可能是偶数。
     * @param s
     * @return
     */
    public String longestPalindrome1(String s) {
    	
    	return "";
    }
    
	/**
	 * 动态规划
	 * @param s
	 * @return
	 */
	public String longestPalindrome2(String s) {
		
		return "";
	}
	
	/**
	 * Manacher 算法
	 * 1、解决字符串奇偶问题（奇数+偶数=奇数）
	 * 2、寻找最大步长和所在的位置索引
	 * 3、根据最大步长和位置索引计算出回文子串的开始索引和结束索引
	 * @param s
	 * @return
	 */
	public String longestPalindrome3(String s) {
		String newString = create(s);
		int length = newString.length();
		int start = 0, end = 0;
		int index = 0;
		int maxStepSize = 0;
		Map<Integer, Integer> map = new HashMap<>();
		for(int i = 0; i < length; i++) {
			int stepSize = 0;
			start = i;
			end = i;
			while(stepSize < ((length / 2) + 1) && start >= 0 && end < length && newString.charAt(start) == newString.charAt(end)) {
				start--;
				end++;
				stepSize++;
			}
			if (stepSize > maxStepSize) {
				maxStepSize = stepSize;
				index = i;
			}
			map.put(i, stepSize);
		}
		System.out.println(map);
		System.out.println("pos " + index + ",maxStepSize " + maxStepSize);
	    return newString.substring(index - (maxStepSize - 1), index + (maxStepSize - 1)).replace("#", "");
	}
	
	public boolean check(String tempString) {
		int index = 0;
		int length = tempString.length();
		if (length % 2 == 0) {
			while(index < (length / 2)) {
				if (tempString.charAt(index) != tempString.charAt(length - index - 1)) {
					return false;
				}
				index++; 
			}
		} else {
			while(index < ((length / 2) + 1)) {
				if (tempString.charAt(index) != tempString.charAt(length - index - 1)) {
					return false;
				}
				index++; 
			}
		}
		return true;
	}
	
	public String create(String s) {
		String divide = "#";
		StringBuffer sb = new StringBuffer();
		sb.append(divide);
		for(int i = 0; i < s.length(); i++) {
			sb.append(s.charAt(i));
			sb.append(divide);
		}
		return sb.toString();
	}
    
    public static void testMethed() {
    	Solution_5 solution = new Solution_5();
    	String s = "abbabb";
    	String longestPalindrome = solution.longestPalindrome(s);
    	System.out.println(longestPalindrome);
    	String longestPalindrome3 = solution.longestPalindrome3(s);
    	System.out.println(longestPalindrome3);
    }
}

/**
 * 题目描述：
 * 	给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。你可以假设 nums1 和 nums2 不会同时为空。
 * 示例：
 * 	nums1 = [1, 3]	nums1 = [1, 2]
 *  nums2 = [2]	nums2 = [3, 4]
 *  则中位数是 2.0	则中位数是 (2 + 3)/2 = 2.5
 * 解题思路：
 * 	中位数概念：中位数是按顺序排列的一组数据中居于中间位置的数。
 * 	解题思路则是先排序后取值
 * @author xiaoxin
 *
 */
class Solution_4 {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    	int[] merge = merge(nums1, nums2);
    	System.out.println("合并之后的数组为：" + Arrays.toString(merge));
    	if(merge.length % 2 == 0) {
    		//偶数
    		return (merge[merge.length / 2] + merge[(merge.length / 2) - 1]) / 2.0;
    	} else {
    		//奇数
    		return merge[merge.length / 2];
    	}
    }
    
    public static int[] merge(int[] left, int[] right) {
		int[] result = new int[left.length + right.length];
		for (int index = 0, i = 0, j = 0; index < result.length; index++) {
			if (i >= left.length)
				result[index] = right[j++];
			else if (j >= right.length)
				result[index] = left[i++];
			else if (left[i] > right[j])
				result[index] = right[j++];
			else
				result[index] = left[i++];
		}
		return result;
	}

    public static void testMethed() {
    	Solution_4 solution = new Solution_4();
    	int[] nums1 = {1, 2, 6, 7, 14, 17};
    	int[] nums2 = {13, 14, 15, 19};
    	double findMedianSortedArrays = solution.findMedianSortedArrays(nums1, nums2);
    	System.out.println(findMedianSortedArrays);
    }
}

/**
 * 题目描述：
 * 	给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
 * 示例：
 * 	输入: "abcabcbb"
 * 	输出: 3 
 *  解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。 
 * 解题思路：
 * 	1、暴力解题
 *  2、
 * @author xiaoxin
 *
 */
class Solution_3 {
	public int lengthOfLongestSubstring(String s) {
    	int maxLength = 0;//子串最大长度
    	int curIndex = 0;//当前索引
    	int curLength = 0;//当前子串长度
    	Set<Character> curCharacters = new HashSet<>();// 记录当前循环子串
    	int length = s.length();
    	for(int i = curIndex; i < length;) {
    		char c = s.charAt(i);
    		if (curCharacters.contains(c)) {
    			maxLength = Math.max(maxLength, curLength);
    			curIndex++;
    			i = curIndex;
    			curCharacters.clear();
    			curLength = 0;
    			continue;
			}
    		curCharacters.add(c);
    		curLength++;
    		i++;
    	}
    	maxLength = Math.max(maxLength, curLength);
        return maxLength;
    }
	
    public int lengthOfLongestSubstring_(String s) {
    	Map<Character, Integer> characters = new HashMap<>();// 记录最长子串
    	Map<Character, Integer> curCharacters = new HashMap<>();// 记录当前循环子串
    	int cruIndex = 0;// 当前循环位置
    	
    	int length = s.length();
    	for(int i = 0; i < length; i++) {
    		curCharacters = new HashMap<>();
    		for(int j = i; j < length; j++) {
    			cruIndex = j;
    			char c = s.charAt(j);
    			if (curCharacters.keySet().contains(c)) {
    				if (characters.size() < curCharacters.size()) {
    					characters = curCharacters; 
    				}
    				break;
				}
    			curCharacters.put(c, j);
    		}
    		if (cruIndex >= length -1) {
    			if (characters.size() < curCharacters.size()) {
    				characters = curCharacters;
    			}
    			break;
    		}
    	}
    	System.out.println(characters);
        return characters.size();
    }
    
    public static void testMethed() {
    	Solution_3 solution = new Solution_3();
    	int lengthOfLongestSubstring = solution.lengthOfLongestSubstring("jabpnbwwd");
    	System.out.println(lengthOfLongestSubstring);
    	int lengthOfLongestSubstring2 = solution.lengthOfLongestSubstring_("aab");
    	System.out.println(lengthOfLongestSubstring2);
    }
}

/**
 * 题目描述：
 * 	给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
 * 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
 * 示例：
 * 	输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
 * 	输出：7 -> 0 -> 8
 * 	原因：342 + 465 = 807
 * 解题思路：
 * 	1、暴力计算
 * 	2、链表转集合
 * @author xiaoxin
 *
 */
class Solution_2 {
	public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
		ListNode listNode = new ListNode(0);
    	ListNode temp1 = l1, temp2 = l2, cruListNode = listNode;
    	int carry = 0;// 溢出值
    	while(temp1 != null || temp2 != null) {
    		int x = temp1 == null ? 0 : temp1.val;
    		int y = temp2 == null ? 0 : temp2.val;
    		int curVal = x + y + carry;
    		carry = curVal / 10;
    		cruListNode.next = new ListNode(curVal % 10);
    		cruListNode = cruListNode.next;
    		if(temp1 != null) temp1 = temp1.next;
    		if(temp2 != null) temp2 = temp2.next;
    	}
    	if(carry > 0) {
    		cruListNode.next = new ListNode(carry);
    		cruListNode = cruListNode.next;
    	}
		return listNode.next;
	}
	
    public ListNode addTwoNumbersList(ListNode l1, ListNode l2) {
    	ListNode listNode = new ListNode(0);
    	ListNode cruListNode = listNode;
    	List<Integer> list1 = ListNodeToList(l1), list2 = ListNodeToList(l2), list = new ArrayList<>();
    	Iterator<Integer> iterator1 = list1.iterator(), iterator2 = list2.iterator();
    	int carry = 0;// 溢出值
    	while(iterator1.hasNext() || iterator2.hasNext()) {
    		int x = iterator1.hasNext() ? iterator1.next() : 0;
    		int y = iterator2.hasNext() ? iterator2.next() : 0;
    		int curVal = x + y + carry;
    		carry = curVal / 10;
    		list.add(curVal % 10);
    	}
    	if (carry > 0) {
			list.add(carry);
		}
    	Iterator<Integer> iterator = list.iterator();
    	while (iterator.hasNext()) {
    		cruListNode.next = new ListNode(iterator.next());
    		cruListNode = cruListNode.next;
		}
    	return listNode.next;
    }
    
    public List<Integer> ListNodeToList(ListNode listNode){
    	List<Integer> list = new ArrayList<>();
    	ListNode temp = listNode;
    	while (temp != null) {
    		list.add(temp.val);
    		temp = temp.next;
    	}
    	return list;
    }
    
    public static void testMethed() {
    	Solution_2 solution = new Solution_2();
    	ListNode l1 = new ListNode(0);
    	ListNode l2 = new ListNode(0); 
    	ListNode c1 = l1,c2 = l2;
    	int i = 3;
    	while(i > 0) {
    		c1.next = new ListNode(8); 
    		c1 = c1.next;
    		
    		c2.next = new ListNode(8); 
    		c2 = c2.next;
    		
    		i--;
    	}
    	
    	ListNode listNode = solution.addTwoNumbersList(l1.next, l2.next);
    	System.out.println(listNode);
    	ListNode node = solution.addTwoNumbers(l1.next, l2.next);
    	System.out.println(node);
    }
    static class ListNode {
    	int val;
    	ListNode next;
    	ListNode(int x) { val = x; }
    }
}

/**
 * 题目描述：
 * 	给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
 * 示例：
 * 	给定 nums = [2, 7, 11, 15], target = 9 
 * 	因为 nums[0] + nums[1] = 2 + 7 = 9 
 * 	所以返回 [0, 1]
 * 理解：
 * 	在一次计算中不能使用已计算过的元素。比如:[1,2,3,2],一次计算过程 1+2；1+3；1+2，最后一个1+2就没必要计算了。
 * 解题思路：
 * 	1、暴力双循环。
 * 	2、转map,hash表计算.
 * 简言之：
 * 	第一次循环原始数组，第二次循环去重数组.
 * @author xiaoxin
 *
 */
class Solution_1 {
    public int[] twoSum(int[] nums, int target) {
        int length = nums.length;
        for(int i = 0; i < length; i++){
            int first = nums[i];
            int temp = target - first;
            for(int j = i + 1; j < length; j++){
                int second = nums[j];
                if(temp == second){
                	int[] result = new int[]{i,j};
                	return result;
                }
            }   
        }
        return null;
    }
    public int[] twoSumMap(int[] nums, int target) {
    	Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i };
            }
            map.put(nums[i], i);
        }
        return null;
    }
    
    public static void testMethed() {
    	Solution_1 solution = new Solution_1();
    	int[] nums = new int[] {3, 2, 4};
    	int target = 6;
    	int[] result = solution.twoSum(nums, target);
    	System.out.println(Arrays.toString(result));
    	int[] resultMap = solution.twoSumMap(nums, target);
    	System.out.println(Arrays.toString(resultMap));
    }
}